At present, a standard method used in order to perform a singular value decomposition in a computer is a DBDSQR routine published by international-known numerical computation library LAPACK. This DBDSQR routine was created based on a QR method and can be divided into three sections; preprocess, main loop and postprocess. The preprocess computes an upper limit and lower limit of a singular value and computes precision used for a convergence criterion. The main loop gradually perform divisions and reductions of a matrix while repeating a QR method and completes a process when the size of the matrix eventually becomes 1×1. When a block of matrix 2×2 appears while the main loop is being performed, another process is performed. The postprocess changes, where computed singular values are changed from negative to positive values. If necessary, the postprocess performs a scalar multiplication on the singular values. The singular values are rearranged in the descending order, and singulars vectors are also rearranged so as to correspond to the singular values. In a DBDSQR, an extremely large amount of computation is required and thus, it is not possible to avoid an increase of time to be required for a computation, especially in a large-scale problem. In a DBDSQR routine, singular values and singular vectors are simultaneously computed. LAPACK publishes a DLASQ routine for computing singular values and a DSTEGR routine for diagonalization, which is used when singular vectors are computed by using the computed singular values. A DLASQ routine can obtain singular values at high speed with high precision. However, it can not compute singular vectors. In view of such a numerical defect, it is difficult to practically use a DSTEGR routine for a singular value decomposition.
Using a DBDSQR routine published by LAPACK as an example, a conventional singular value decomposition method will be described. A DBDSQR routine first applies a Householder transformation to standard matrix A having l1×l2 in order to perform a singular value decomposition on the matrix A. In other words, the matrix A can be represented by using orthogonal matrices UA and UV as:
                                          U            A            T                    ⁢                      AV            A                          =                  {                                                                                          (                                          B                      ⁢                                                                                          ⁢                      0                                        )                                                                                        (                                                                  l                        1                                            ≤                                              l                        2                                                              )                                                                                                                    (                                                                                            B                                                                                                                      0                                                                                      )                                                                                        (                                                                  l                        1                                            ≥                                              l                        2                                                              )                                                                        ,                                                  ⁢                          B              =                                                                    (                                                                                                                        b                            1                                                                                                                                b                            2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            b                            3                                                                                                    ⋱                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ⋱                                                                                                      b                                                                                          2                                ⁢                                m                                                            -                              2                                                                                                                                                                            0                                                                                                                                                                                                                                                                                                                                                                      b                                                                                          2                                ⁢                                m                                                            -                              1                                                                                                                                            )                                    ⁢                                                                          ⁢                                      U                    A                    T                                    ⁢                                      U                    A                                                  =                I                                      ,                                                  ⁢                                                            V                  A                  T                                ⁢                                  V                  A                                            =              I                        ,                                                  ⁢                          m              =                              min                ⁢                                  {                                                            l                      1                                        ,                                          l                      2                                                        }                                                                                        [                  Expression          ⁢                                          ⁢          4                ]            
B obtained in this case is called upper bidiagonal matrix. Herein, it should be noted that a singular value of A=a singular value of B. Accordingly, a singular value decomposition problem for the standard matrix A is replaced with a singular value decomposition problem for upper bidiagonal matrix BTB,B=UBΣVBT 
where matrices UB and VB are left and right orthogonal matrices, respectively,
Σ≡diag(σ1, σ2, . . . , σm)σ1≧σ2≧ . . . σm≧0, and
σj is a singular value of B.
Next, matrix BTB will be considered. Diagonalization of this matrix B is performed by:Λ=VTBTBV 
where Λ≡diag(λ1, λ2, . . . , λm) λ1≧λ2≧ . . . λm≧0
V≡(v1, v2, . . . , vm)
λj is an eigenvalue of BTB, and
vj is an eigenvector for the eigenvalue λj.
Herein, the following is normally established: (1) BTB is a symmetric tridiagonal matrix; (2) Eigenvalues of BTB are all positive, and singular value σj (σ1≧σ2≧ . . . ≧σm≧0) of B is equal to a positive square root of eigenvalue λj (λ1≧λ2≧ . . . ≧λm≧0) of BTB; (3) VB=V, i.e., eigenvector vj of BTB is equal to a right singular vector of B. Accordingly, when the diagonalization of the matrix BTB has been obtained, Σ is obtained since Λ=Σ2 from (2), and further, left orthogonal matrix UB=BVBΣ−1=BVΣ−1 is obtained from (3). Therefore, B is singular-value-decomposed. In other words, the singular value decomposition of B can be replaced with a problem of diagonalization of BTB. Not only can this principle be applied to obtaining all m number of singular values and singular vectors, but also this principle can be applied to obtaining at least one singular value and singular vector.
As described above, the singular value decomposition of the standard matrix A includes the problem of diagonalization of the symmetric tridiagonal matrix BTB.